package demo.practice.leetcode_base;

public class P53 {


    // [-2,1,-3,4,-1,2,1,-5,4]
    //位置        之前和（）       当前值     最大和
    //0             0           -2         -2
    //1             -2          1           1
    //2             1           -3          1
    //3            -

    public static void main(String[] args) {
        int a[]= new int[]{-2,1,-3,4,-1,2,1,-5,4};
        P53 p53= new P53();
        p53.maxSubArray(a);

    }

    public int maxSubArray2(int[] nums) {
        int sum_befor=0;
        int sum_max=Integer.MIN_VALUE;

        for(int i=0;i<nums.length;i++){
            if(sum_befor+nums[i]>sum_max)
                sum_max=sum_befor+nums[i];

            if(sum_befor+nums[i]>0)
                sum_befor=sum_befor+nums[i];
            else
                sum_befor=0;
        }
        return sum_max;
    }


    public int maxSubArray(int[] nums) {
        int sum_current=nums.length>0? nums[0] :Integer.MIN_VALUE;
        int befor=0;

        for(int i=0;i<nums.length;i++){

           if(befor>=0)
               befor=befor+nums[i];
           else
               befor=nums[i];

           if(befor>sum_current)
               sum_current=befor;
        }
        return  sum_current;
    }

}
